﻿#ifndef ABSolver_CPP
#define ABSolver_CPP
#define MIN -100000000
#define MAX 100000000
#define ALPHA -100000000
#define BEAT 100000000
#define BETA 100000000
#define UNKNOW -1000000000
#define UNKONW_PAIR {{-100, -100, -100}, -1000000000}
#include "TemplateSolver.cpp"
/*#define HASH true*/ // 使用置换表设置为true
//#define MT true // 使用多线程设置为true
#include <algorithm>
#include <ctime>
#include <random>
#include "ChainTable.h"
#include <unordered_map>
#include <thread>
#include <mutex>
#include "HashTable.h"
using std::thread;
using std::unordered_map;
using std::mutex;



// alpha-beta purning 算法, 目前证明多线程几乎没用; 另外如果想参考我们的算法, 第一遍请先无视宏定义MT与HASH中的内容
class ABSolver : public TemplateSolver
{

private:
    int start;

    int max_level;

public:
    unordered_map<size_t, int> _c_1;
    unordered_map<size_t, vector<Step>> _c_2;

#ifdef MT
    mutex mtx;

    thread th1;

    thread th2;

    thread th3;

#endif // MT



    unordered_map<size_t, hitem>* htable;

    double move_time = 6.5;

    Pair cur_best;

    int nc = 0;

    int hc = 0;

    int reference_player;

    int max_deep = 0;


    ABSolver()
    {
        this->htable = HashTable::getTable()->get_map();
    }

    //记录hash
    void record_hash(Frame* frame, hitem item)
    {
        size_t key = frame->get_hash();
    }

    //记录hash
    void record_hash(size_t key, hitem item)
    {
        //先查一遍是不是在表中
#ifdef MT
        mtx.lock();
#endif // MT
        unordered_map<size_t, hitem>::iterator iter = htable->find(key);
        hitem item_;
        if (iter != htable->end())
        {
            //表中查到
            item_ = iter->second;
            item_.flag = item.flag;
            //如果表中的深度比现在的深就直接pass
            if (item_.depth > item.depth)
            {
#ifdef MT
                mtx.unlock();
#endif // MT
                return;
            }
            //如果表中的深度比现在的浅就更新
            item_.depth = item.depth;
            item_.step = item.step;
            item_.utility = item.utility;
            item_.flag = item.flag;
        }

        //没查到直接设置
        htable->insert(std::make_pair(key, item));

#ifdef MT
        mtx.unlock();
#endif // MT
    }

    //hash探针
    Pair probe_hash(size_t key, int depth, Pair pair)
    {

        //hitem& item = htable[key];
#ifdef MT
        mtx.lock();
#endif // MT

        unordered_map<size_t, hitem>::iterator iter = htable->find(key);
        hitem item;
        if (iter != htable->end())
        {
            item = iter->second;
        }
        else
        {
#ifdef MT
            mtx.unlock();
#endif // MT
            return Pair(UNKONW_PAIR);
        }

        //如果记录过
        if (item.is_know == 1)
        {
            //如果置换表中的项的深度大于传入的深度, 就返回表中的
            if (item.depth >= (-depth))
            {
                if (item.flag == hashfEXACT)
                {
#ifdef MT
                    mtx.unlock();
#endif // MT
                    return Pair({ item.step, item.utility });
                }
                else if ((item.flag == hashfALPHA) && (item.utility <= ALPHA))
                {
#ifdef MT
                    mtx.unlock();
#endif // MT
                    return Pair({ item.step, ALPHA });
                }
                else if ((item.flag == hashfBETA) && (item.utility >= BEAT))
                {
#ifdef MT
                    mtx.unlock();
#endif // MT
                    return Pair({ item.step, BEAT });
                }
            }

        }

        //如果没记录过, 则返回一个UNKONW_PAIR
#ifdef MT
        mtx.unlock();
#endif // MT
        return Pair(UNKONW_PAIR);
    }

    //hash探针
    Pair probe_hash(size_t key, int depth, int alpha, int beta)
    {

        //hitem& item = htable[key];
#ifdef MT
        mtx.lock();
#endif // MT

        unordered_map<size_t, hitem>::iterator iter = htable->find(key);
        hitem item;
        if (iter != htable->end())
        {
            item = iter->second;
        }
        else
        {
#ifdef MT
            mtx.unlock();
#endif // MT
            return Pair(UNKONW_PAIR);
        }

        //如果记录过
        if (item.is_know == 1)
        {
            //如果置换表中的项的深度大于传入的深度, 就返回表中的
            if (item.depth >= (-depth))
            {
                if (item.flag == hashfEXACT)
                {
#ifdef MT
                    mtx.unlock();
#endif // MT
                    hc++;
                    return Pair({ item.step, item.utility });
                }
                else if ((item.flag == hashfALPHA) && (item.utility <= alpha))
                {
#ifdef MT
                    mtx.unlock();
#endif // MT
                    return Pair({ item.step, alpha });
                }
                else if ((item.flag == hashfBETA) && (item.utility >= beta))
                {
#ifdef MT
                    mtx.unlock();
#endif // MT
                    return Pair({ item.step, beta });
                }
            }

        }

        //如果没记录过, 则返回一个UNKONW_PAIR
#ifdef MT
        mtx.unlock();
#endif // MT
        return Pair(UNKONW_PAIR);
    }


    virtual Step solve(Frame* frame)
    {
        return ab_gen_next_step(frame);
    }

    /**
     * @brief alphaBeta剪枝生成下一步
     *
     * @param Frame 当前回合帧
     * @return Step 步伐
     */
    Step ab_gen_next_step(Frame* frame)
    {
        nc = 0;
        hc = 0;
        max_deep = 0;
        start = (int)std::time(0);
        reference_player = frame->turn;
        max_level = 1;
        Step best_step;
        best_step.dir = -1;
        best_step.x = -1;
        best_step.y = -1;

        printf("[ABSolver]: 实际棋盘未落边时的安全步数--[%d]\n", get_remain_safe_count(frame->cur_board));
#ifdef MT
        th1 = attach_cal_thread(frame);
        th1.detach();
        th2 = attach_cal_thread(frame);
        th2.detach();
        th3 = attach_cal_thread(frame);
        th3.detach();
#endif // MT


        while (max_level <= (int)(frame->cur_board->get_available_steps().size()))
        {


            Pair pair = new_dfs(frame, ALPHA, BETA, 0);

            if ((int)std::time(0) - start < move_time)
                best_step = pair.step;
            else
                break;
            //相对于当前节点的搜索深度
            max_level += 1;
            cur_best = { best_step, pair.utility };
            printf("[ABSolver]: 当前第[%d]层最优步数的分为[%d] --",max_level - 1,cur_best.utility);
            printf("[%d, %d, %d]\n", best_step.dir, best_step.x, best_step.y);
        };
        printf("[ABSolver]: 进入dfs的次数: %d\n", nc);
        double rate = double(hc) / double(nc);
        return best_step;
    }


    Pair new_dfs(Frame* frame, int a, int b, int level)
    {
        max_deep = level > max_deep ? level : max_deep;


        //单纯计数
        nc++;

        // 当深度小于max_level 并且没有超过时间限制时
        if ((level < max_level && ((int)std::time(0) - start < move_time)))
        {
            //不上锁会导致内存爆炸 暂不知道原因

#ifdef MT
            //mtx.lock();
#endif // MT

            ChainTable* table = new ChainTable(frame->cur_board);
            std::vector<Step>* steps = new std::vector<Step>(table->dedup_step_of_chain());
            int size = steps->size();
            delete table;

            //打乱steps
            std::random_device seed;
            auto rng = std::default_random_engine{ seed() };
            std::shuffle(steps->begin(), steps->end(), rng);
#ifdef MT
            //mtx.unlock();
#endif // MT

            if (size == 0)
            {
                //返回叶子节点
                Step step = { -1, -1, -1 };
                int utility = evaluate(frame);
                Pair pair;
                pair.step = step;
                pair.utility = utility;
                delete steps;
#ifdef HASH
                record_hash(frame->get_hash(), hitem(-level, pair, hashfEXACT));
#endif // HASH
                return pair;
            }

            //儿子节点容器
            std::vector<Pair>* neighbors = new std::vector<Pair>();
            for (int i = 0; i < size; i++)
            {
                Board* new_board = frame->cur_board->get_new_board(frame->turn, steps->at(i).dir, steps->at(i).x, steps->at(i).y);
                //新回合的是谁
                int new_round_player = new_board->get_current_player_score(frame->turn) > frame->cur_board->get_current_player_score(frame->turn) ? frame->turn : frame->toggle_round(frame->turn);
                Frame* eva_frame = new Frame(new_round_player, new_board->get_current_player_score(RED_), new_board->get_current_player_score(BLUE_), new_board);
                neighbors->push_back(Pair({ steps->at(i), evaluate(eva_frame) }));
                delete new_board;
                delete eva_frame;
            }

            std::sort(neighbors->begin(), neighbors->end());
            std::vector<Step>* steps_ = new std::vector<Step>();
            if (reference_player != frame->turn)
                for (int i = 0; i < size; i++)
                    steps_->push_back(neighbors->at(i).step);
            else
                for (int i = size - 1; i >= 0; i--)
                    steps_->push_back(neighbors->at(i).step);

            if (frame->turn == reference_player)
            {
                //max 层是我们的回合 修改alpha的值
                Pair new_pair = { Step{-1, -1, -1}, ALPHA };
                for (int i = 0; i < size; i++)
                {
                    //遍历所有子节点
                    Board* child_board = frame->cur_board->get_new_board(frame->turn, steps_->at(i).dir, steps_->at(i).x, steps_->at(i).y);
                    int child_score = child_board->get_current_player_score(frame->turn);
                    int current_score = frame->cur_board->get_current_player_score(frame->turn);
                    bool flag = false;
                    Pair pair;
                    if (child_score == current_score)
                    {
                        Frame* new_frame = new Frame(frame->toggle_round(frame->turn), child_board->get_current_player_score(RED_), child_board->get_current_player_score(BLUE_), child_board);

#ifdef HASH
                        bool flag_h = false;
                        Pair table_best = probe_hash(new_frame->get_hash(), level, a, b);
                        //Pair table_best = probe_hash(new_frame->get_hash(), level, cur_best);
                        if (table_best.utility != UNKNOW)
                        {
                            //如果这一步在可行步中就返回
                            for (int i = 0; i < size; i++)
                            {
                                if (table_best.step.dir == steps->at(i).dir && table_best.step.x == steps->at(i).x && table_best.step.y == steps->at(i).y)
                                {
                                    pair = table_best;
                                    flag_h = true;
                                    break;
                                }
                            }

                        }
#endif // HASH

#ifdef HASH
                        if (flag_h == false) // 如果在表中没找到, 则dfs
                        {
#endif // HASH
                            pair = new_dfs(new_frame, a, b, level + 1);
#ifdef HASH
                            //record_hash(new_frame->get_hash(), hitem(-(level + 1), pair, hashfALPHA)); //换手, 转到min层, 标记为hashfALPHA说明对于这个子节点来说, 其评价值至多为pair.utility
                        }
#endif // HASH
                        delete new_frame->cur_board;
                        delete new_frame;
                        flag = true;
                    }
                    else {
                        Frame* new_frame = new Frame(frame->turn, child_board->get_current_player_score(RED_), child_board->get_current_player_score(BLUE_), child_board);

#ifdef HASH
                        bool flag_h = false;
                        Pair table_best = probe_hash(new_frame->get_hash(), level, a, b);
                        //Pair table_best = probe_hash(new_frame->get_hash(), level, cur_best);
                        if (table_best.utility != UNKNOW)
                        {
                            //如果这一步在可行步中就返回
                            for (int i = 0; i < size; i++)
                            {
                                if (table_best.step.dir == steps->at(i).dir && table_best.step.x == steps->at(i).x && table_best.step.y == steps->at(i).y)
                                {
                                    pair = table_best;
                                    flag_h = true;
                                    break;
                                }
                            }

                        }
#endif // HASH

#ifdef HASH
                        if (flag_h == false)
                        {
#endif // HASH
                            pair = new_dfs(new_frame, a, b, level + 1);
#ifdef HASH
                            //record_hash(new_frame->get_hash(), hitem(-(level + 1), pair, hashfBETA)); //不换手, 还是max层, 标记为hashfBETA表示对于这个子节点来说, 其评价值至少为pair.utility
                        }
#endif // HASH
                        delete new_frame->cur_board;
                        delete new_frame;
                    }
                    //选择一个对我们最有利的步伐
                    int child_utility = pair.utility;
                    if (new_pair.utility < child_utility)
                        new_pair = Pair({ steps_->at(i), child_utility });
                    if (flag) // 如果换手了(接下来会转为min层)
                        if (child_utility >= b) { // alpha >= beta 了, 剪枝 test
                        //if (new_pair.utility >= b) { // alpha >= beta 了, 剪枝
                            delete steps_;
                            delete neighbors;
                            delete steps;
#ifdef HASH
                            //record_hash(frame->get_hash(), hitem(-level, new_pair, hashfEXACT)); // 这一步的值是准确的
#endif // HASH
                            return new_pair;
                        }
//#ifdef HASH
//                    if (new_pair.utility > a)
//                        hashf = hashfEXACT;
//#endif // HASH
                    //子节点向上传递alpha值
                    a = a > new_pair.utility ? a : new_pair.utility;


                }

                delete steps_;
                delete neighbors;
                delete steps;
#ifdef HASH
                //子节点已经遍历完了, 那么对于这个节点记录到置换表里面的一定是准的
                record_hash(frame->get_hash(), hitem(-level, new_pair, hashfEXACT));
#endif // HASH
                return new_pair;
            }
            else
            {
                //MIN层对手回合 对方修改beta的值
                Pair new_pair = { Step({-1, -1, -1}), BETA };
                for (int i = 0; i < size; i++)
                {
                    //遍历所有子节点
                    Board* child_board = frame->cur_board->get_new_board(frame->turn, steps_->at(i).dir, steps_->at(i).x, steps_->at(i).y);
                    int child_score = child_board->get_current_player_score(frame->turn);
                    int current_score = frame->cur_board->get_current_player_score(frame->turn);
                    bool flag = false;
                    Pair pair;
                    if (child_score == current_score)
                    {
                        Frame* new_frame = new Frame(frame->toggle_round(frame->turn), child_board->get_current_player_score(RED_), child_board->get_current_player_score(BLUE_), child_board);

#ifdef HASH
                        bool flag_h = false;
                        Pair table_best = probe_hash(new_frame->get_hash(), level, a, b);
                        //Pair table_best = probe_hash(new_frame->get_hash(), level, cur_best);
                        if (table_best.utility != UNKNOW)
                        {
                            //如果这一步在可行步中就返回
                            for (int i = 0; i < size; i++)
                            {
                                if (table_best.step.dir == steps->at(i).dir && table_best.step.x == steps->at(i).x && table_best.step.y == steps->at(i).y)
                                {
                                    pair = table_best;
                                    flag_h = true;
                                    break;
                                }
                            }

                        }
#endif // HASH

#ifdef HASH
                        if (flag_h == false)
                        {
#endif // HASH
                            pair = new_dfs(new_frame, a, b, level + 1);
#ifdef HASH
                            //record_hash(new_frame->get_hash(), hitem(-(level + 1), pair, hashfBETA)); //换手, 转到max层, 标记为hashfBETA表示对于这个节点来说至少为其评价值至少为pair.utility
                        }
#endif // HASH
                        delete new_frame->cur_board;
                        delete new_frame;
                        flag = true;
                    }
                    else {
                        Frame* new_frame = new Frame(frame->turn, child_board->get_current_player_score(RED_), child_board->get_current_player_score(BLUE_), child_board);
#ifdef HASH
                        bool flag_h = false;
                        Pair table_best = probe_hash(new_frame->get_hash(), level, a, b);
                        //Pair table_best = probe_hash(new_frame->get_hash(), level, cur_best);
                        if (table_best.utility != UNKNOW)
                        {
                            //如果这一步在可行步中就返回
                            for (int i = 0; i < size; i++)
                            {
                                if (table_best.step.dir == steps->at(i).dir && table_best.step.x == steps->at(i).x && table_best.step.y == steps->at(i).y)
                                {
                                    pair = table_best;
                                    flag_h = true;
                                    break;
                                }
                            }

                        }
#endif // HASH

#ifdef HASH
                        if (flag_h == false)
                        {
#endif // HASH
                            pair = new_dfs(new_frame, a, b, level + 1);
#ifdef HASH
                            //record_hash(new_frame->get_hash(), hitem(-(level + 1), pair, hashfALPHA)); //不换手, 依然是min层, 标记为hashfALPHA表示对于这个子节点来说其评价值至多为其评价值至多为pair.utility
                        }
#endif // HASH
                        delete new_frame->cur_board;
                        delete new_frame;
                    }

                    int child_utility = pair.utility;
                    if (new_pair.utility > child_utility)
                        new_pair = Pair({ steps_->at(i), child_utility });
                    if (flag)
                        if (child_utility <= a) { //alpha大于beta, 剪枝 test
                        //if (new_pair.utility <= a) { //alpha大于beta, 剪枝
                            delete steps_;
                            delete neighbors;
                            delete steps;
#ifdef HASH
                            //record_hash(frame->get_hash(), hitem(-level, new_pair, hashfEXACT));
#endif // HASH
                            return new_pair;
                        }

//#ifdef HASH
//                    if (new_pair.utility < b)
//                        hashf = hashfEXACT;
//#endif // HASH
                    //子节点向上传递beta值(求min)
                    b = b < new_pair.utility ? b : new_pair.utility;
                }

                delete steps_;
                delete neighbors;
                delete steps;

#ifdef HASH
                //节点已经遍历完了, 那么对于这个节点记录到置换表里面的一定是准的
                record_hash(frame->get_hash(), hitem(-level, new_pair, hashfEXACT));
#endif // HASH
                return new_pair;
            }
        }
        else {
            //如果到达底层或者时间到了, 直接返回评估
            return Pair({ Step({-1, -1, -1}), evaluate(frame) });
        }
    }


    //以前版本未优化的dfs, 参考意义已经不大
    Pair dfs(Frame* frame, int a, int b, int level)
    {
        // 当深度小于max_level 并且没有超过时间限制时
        if (level < max_level && ((int)std::time(0) - start < move_time))
        {
            std::vector<Step>* steps = new std::vector<Step>(frame->cur_board->get_available_steps());
            int size = steps->size();

            //打乱steps
            std::random_device seed;
            auto rng = std::default_random_engine{ seed() };
            std::shuffle(steps->begin(), steps->end(), rng);

            if (size == 0)
            {
                //返回叶子节点
                Step step = { -1, -1, -1 };
                int utility = evaluate(frame);
                Pair pair;
                pair.step = step;
                pair.utility = utility;
                delete steps;
                return pair;
            }

            //儿子节点容器
            std::vector<Pair>* neighbors = new std::vector<Pair>();
            for (int i = 0; i < size; i++)
            {
                Board* new_board = frame->cur_board->get_new_board(frame->turn, steps->at(i).dir, steps->at(i).x, steps->at(i).y);
                //新回合的是谁
                int new_round_player = new_board->get_current_player_score(frame->turn) > frame->cur_board->get_current_player_score(frame->turn) ? frame->turn : frame->toggle_round(frame->turn);
                Frame* eva_frame = new Frame(new_round_player, new_board->get_current_player_score(RED_), new_board->get_current_player_score(BLUE_), new_board);
                neighbors->push_back(Pair({ steps->at(i), evaluate(eva_frame) }));
                delete new_board;
                delete eva_frame;
            }

            // TODO 暂时不知道排序顺序
            std::sort(neighbors->begin(), neighbors->end());
            std::vector<Step>* steps_ = new std::vector<Step>();
            if (reference_player != frame->turn)
                for (int i = 0; i < size; i++)
                    steps_->push_back(neighbors->at(i).step);
            else
                for (int i = size - 1; i >= 0; i--)
                    steps_->push_back(neighbors->at(i).step);

            if (frame->turn == reference_player)
            {
                //max 层是我们的回合

                Pair new_pair = { Step{-1, -1, -1}, MIN };
                for (int i = 0; i < size; i++)
                {
                    //遍历所有子节点
                    Board* child_board = frame->cur_board->get_new_board(frame->turn, steps_->at(i).dir, steps_->at(i).x, steps_->at(i).y);
                    int child_score = child_board->get_current_player_score(frame->turn);
                    int current_score = frame->cur_board->get_current_player_score(frame->turn);
                    bool flag = false;
                    Pair pair;
                    if (child_score == current_score)
                    {
                        Frame* new_frame = new Frame(frame->toggle_round(frame->turn), child_board->get_current_player_score(RED_), child_board->get_current_player_score(BLUE_), child_board);
                        pair = dfs(new_frame, a, b, level + 1);
                        delete new_frame->cur_board;
                        delete new_frame;
                        flag = true;
                    }
                    else {
                        Frame* new_frame = new Frame(frame->turn, child_board->get_current_player_score(RED_), child_board->get_current_player_score(BLUE_), child_board);
                        pair = dfs(new_frame, a, b, level + 1);
                        delete new_frame->cur_board;
                        delete new_frame;
                    }

                    int child_utility = pair.utility;
                    if (new_pair.utility < child_utility)
                        new_pair = Pair({ steps_->at(i), child_utility });
                    if (flag)
                        if (child_utility >= b) {
                            delete steps_;
                            delete neighbors;
                            delete steps;
                            return new_pair;
                        }

                    a = a > new_pair.utility ? a : new_pair.utility;
                }

                delete steps_;
                delete neighbors;
                delete steps;
                return new_pair;
            }
            else
            {
                //MIN层对手回合

                Pair new_pair = { Step({-1, -1, -1}), MAX };
                for (int i = 0; i < size; i++)
                {
                    //遍历所有子节点
                    Board* child_board = frame->cur_board->get_new_board(frame->turn, steps_->at(i).dir, steps_->at(i).x, steps_->at(i).y);
                    int child_score = child_board->get_current_player_score(frame->turn);
                    int current_score = frame->cur_board->get_current_player_score(frame->turn);
                    bool flag = false;
                    Pair pair;
                    if (child_score == current_score)
                    {
                        Frame* new_frame = new Frame(frame->toggle_round(frame->turn), child_board->get_current_player_score(RED_), child_board->get_current_player_score(BLUE_), child_board);
                        pair = dfs(new_frame, a, b, level + 1);

                        delete new_frame->cur_board;
                        delete new_frame;
                        flag = true;
                    }
                    else {
                        Frame* new_frame = new Frame(frame->turn, child_board->get_current_player_score(RED_), child_board->get_current_player_score(BLUE_), child_board);
                        pair = dfs(new_frame, a, b, level + 1);
                        delete new_frame->cur_board;
                        delete new_frame;
                    }

                    int child_utility = pair.utility;
                    if (new_pair.utility > child_utility)
                        new_pair = Pair({ steps_->at(i), child_utility });
                    if (flag)
                        if (child_utility <= a) {
                            delete steps_;
                            delete neighbors;
                            delete steps;
                            return new_pair;
                        }

                    b = b < new_pair.utility ? b : new_pair.utility;

                }

                delete steps_;
                delete neighbors;
                delete steps;
                return new_pair;
            }
        }
        else {
            return Pair({ Step({-1, -1, -1}), evaluate(frame) });
        }
    }

    virtual void change_move_time(double times)
    {
        this->move_time = times;
    }

    virtual void record_solver_info(std::string path)
    {

    }

    thread attach_cal_thread(Frame* frame)
    {
        int cur_deep = frame->cur_board->get_available_steps().size();

        return thread(static_cast<Pair(ABSolver::*)(Frame * frame, int a, int b, int level)>(&ABSolver::cal_dfs), this, frame, ALPHA, BETA, 0);
    }


    Pair cal_dfs(Frame* frame, int a, int b, int level)
    {
        // 当深度小于max_level 并且没有超过时间限制时
        //if (level < max_level && ((int)std::time(0) - start < move_time))
        if (level < (max_level + 2) && ((int)std::time(0) - start < move_time))
        {
            //不上锁会导致内存爆炸 占不知道原因

#ifdef MT
            mtx.lock();
#endif // MT

            ChainTable* table = new ChainTable(frame->cur_board);
            std::vector<Step>* steps = new std::vector<Step>(table->dedup_step_of_chain());
            int size = steps->size();
            delete table;

            //打乱steps
            std::random_device seed;
            auto rng = std::default_random_engine{ seed() };
            std::shuffle(steps->begin(), steps->end(), rng);
#ifdef MT
            mtx.unlock();
#endif // MT

            if (size == 0)
            {
                //返回叶子节点
                Step step = { -1, -1, -1 };
                int utility = evaluate(frame);
                Pair pair;
                pair.step = step;
                pair.utility = utility;
                delete steps;
#ifdef HASH
                record_hash(frame->get_hash(), hitem(-level, pair, hashfEXACT));
#endif // HASH
                return pair;
            }

            //儿子节点容器
            std::vector<Pair>* neighbors = new std::vector<Pair>();
            for (int i = 0; i < size; i++)
            {
                Board* new_board = frame->cur_board->get_new_board(frame->turn, steps->at(i).dir, steps->at(i).x, steps->at(i).y);
                //新回合的是谁
                int new_round_player = new_board->get_current_player_score(frame->turn) > frame->cur_board->get_current_player_score(frame->turn) ? frame->turn : frame->toggle_round(frame->turn);
                Frame* eva_frame = new Frame(new_round_player, new_board->get_current_player_score(RED_), new_board->get_current_player_score(BLUE_), new_board);
                neighbors->push_back(Pair({ steps->at(i), evaluate(eva_frame) }));
                delete new_board;
                delete eva_frame;
            }

            std::sort(neighbors->begin(), neighbors->end());
            std::vector<Step>* steps_ = new std::vector<Step>();
            if (reference_player != frame->turn)
                for (int i = 0; i < size; i++)
                    steps_->push_back(neighbors->at(i).step);
            else
                for (int i = size - 1; i >= 0; i--)
                    steps_->push_back(neighbors->at(i).step);

            if (frame->turn == reference_player)
            {
                //max 层是我们的回合 修改alpha的值
                Pair new_pair = { Step{-1, -1, -1}, ALPHA };
                for (int i = 0; i < size; i++)
                {
                    //遍历所有子节点
                    Board* child_board = frame->cur_board->get_new_board(frame->turn, steps_->at(i).dir, steps_->at(i).x, steps_->at(i).y);
                    int child_score = child_board->get_current_player_score(frame->turn);
                    int current_score = frame->cur_board->get_current_player_score(frame->turn);
                    bool flag = false;
                    Pair pair;
                    if (child_score == current_score)
                    {
                        Frame* new_frame = new Frame(frame->toggle_round(frame->turn), child_board->get_current_player_score(RED_), child_board->get_current_player_score(BLUE_), child_board);

#ifdef HASH
                        bool flag_h = false;
                        Pair table_best = probe_hash(new_frame->get_hash(), level, a, b);
                        //Pair table_best = probe_hash(new_frame->get_hash(), level, cur_best);
                        if (table_best.utility != UNKNOW)
                        {
                            //如果这一步在可行步中就返回
                            for (int i = 0; i < size; i++)
                            {
                                if (table_best.step.dir == steps->at(i).dir && table_best.step.x == steps->at(i).x && table_best.step.y == steps->at(i).y)
                                {
                                    pair = table_best;
                                    flag_h = true;
                                    break;
                                }
                            }

                        }
#endif // HASH

#ifdef HASH
                        if (flag_h == false) // 如果在表中没找到, 则dfs
                        {
#endif // HASH
                            pair = cal_dfs(new_frame, a, b, level + 1);
#ifdef HASH
                            //record_hash(new_frame->get_hash(), hitem(-(level + 1), pair, hashfALPHA)); //换手, 转到min层, 标记为hashfALPHA说明对于这个子节点来说, 其评价值至多为pair.utility
                        }
#endif // HASH
                        delete new_frame->cur_board;
                        delete new_frame;
                        flag = true;
                    }
                    else {
                        Frame* new_frame = new Frame(frame->turn, child_board->get_current_player_score(RED_), child_board->get_current_player_score(BLUE_), child_board);

#ifdef HASH
                        bool flag_h = false;
                        Pair table_best = probe_hash(new_frame->get_hash(), level, a, b);
                        //Pair table_best = probe_hash(new_frame->get_hash(), level, cur_best);
                        if (table_best.utility != UNKNOW)
                        {
                            //如果这一步在可行步中就返回
                            for (int i = 0; i < size; i++)
                            {
                                if (table_best.step.dir == steps->at(i).dir && table_best.step.x == steps->at(i).x && table_best.step.y == steps->at(i).y)
                                {
                                    pair = table_best;
                                    flag_h = true;
                                    break;
                                }
                            }

                        }
#endif // HASH

#ifdef HASH
                        if (flag_h == false)
                        {
#endif // HASH
                            pair = cal_dfs(new_frame, a, b, level + 1);
#ifdef HASH
                            //record_hash(new_frame->get_hash(), hitem(-(level + 1), pair, hashfBETA)); //不换手, 还是max层, 标记为hashfBETA表示对于这个子节点来说, 其评价值至少为pair.utility
                        }
#endif // HASH
                        delete new_frame->cur_board;
                        delete new_frame;
                    }
                    //选择一个对我们最有利的步伐
                    int child_utility = pair.utility;
                    if (new_pair.utility < child_utility)
                        new_pair = Pair({ steps_->at(i), child_utility });
                    if (flag) // 如果换手了(接下来会转为min层)
                        if (child_utility >= b) { // alpha >= beta 了, 剪枝
                            delete steps_;
                            delete neighbors;
                            delete steps;
#ifdef HASH
                            //record_hash(frame->get_hash(), hitem(-level, new_pair, hashfEXACT)); // 这一步的值是准确的
#endif // HASH
                            return new_pair;
                        }
                    //#ifdef HASH
                    //                    if (new_pair.utility > a)
                    //                        hashf = hashfEXACT;
                    //#endif // HASH
                                        //子节点向上传递alpha值
                    a = a > new_pair.utility ? a : new_pair.utility;


                }

                delete steps_;
                delete neighbors;
                delete steps;
#ifdef HASH
                //子节点已经遍历完了, 那么对于这个节点记录到置换表里面的一定是准的
                record_hash(frame->get_hash(), hitem(-level, new_pair, hashfEXACT));
#endif // HASH
                return new_pair;
            }
            else
            {
                //MIN层对手回合 对方修改beta的值
                Pair new_pair = { Step({-1, -1, -1}), BETA };
                for (int i = 0; i < size; i++)
                {
                    //遍历所有子节点
                    Board* child_board = frame->cur_board->get_new_board(frame->turn, steps_->at(i).dir, steps_->at(i).x, steps_->at(i).y);
                    int child_score = child_board->get_current_player_score(frame->turn);
                    int current_score = frame->cur_board->get_current_player_score(frame->turn);
                    bool flag = false;
                    Pair pair;
                    if (child_score == current_score)
                    {
                        Frame* new_frame = new Frame(frame->toggle_round(frame->turn), child_board->get_current_player_score(RED_), child_board->get_current_player_score(BLUE_), child_board);

#ifdef HASH
                        bool flag_h = false;
                        Pair table_best = probe_hash(new_frame->get_hash(), level, a, b);
                        //Pair table_best = probe_hash(new_frame->get_hash(), level, cur_best);
                        if (table_best.utility != UNKNOW)
                        {
                            //如果这一步在可行步中就返回
                            for (int i = 0; i < size; i++)
                            {
                                if (table_best.step.dir == steps->at(i).dir && table_best.step.x == steps->at(i).x && table_best.step.y == steps->at(i).y)
                                {
                                    pair = table_best;
                                    flag_h = true;
                                    break;
                                }
                            }

                        }
#endif // HASH

#ifdef HASH
                        if (flag_h == false)
                        {
#endif // HASH
                            pair = cal_dfs(new_frame, a, b, level + 1);
#ifdef HASH
                            //record_hash(new_frame->get_hash(), hitem(-(level + 1), pair, hashfBETA)); //换手, 转到max层, 标记为hashfBETA表示对于这个节点来说至少为其评价值至少为pair.utility
                        }
#endif // HASH
                        delete new_frame->cur_board;
                        delete new_frame;
                        flag = true;
                    }
                    else {
                        Frame* new_frame = new Frame(frame->turn, child_board->get_current_player_score(RED_), child_board->get_current_player_score(BLUE_), child_board);
#ifdef HASH
                        bool flag_h = false;
                        Pair table_best = probe_hash(new_frame->get_hash(), level, a, b);
                        //Pair table_best = probe_hash(new_frame->get_hash(), level, cur_best);
                        if (table_best.utility != UNKNOW)
                        {
                            //如果这一步在可行步中就返回
                            for (int i = 0; i < size; i++)
                            {
                                if (table_best.step.dir == steps->at(i).dir && table_best.step.x == steps->at(i).x && table_best.step.y == steps->at(i).y)
                                {
                                    pair = table_best;
                                    flag_h = true;
                                    break;
                                }
                            }

                        }
#endif // HASH

#ifdef HASH
                        if (flag_h == false)
                        {
#endif // HASH
                            pair = cal_dfs(new_frame, a, b, level + 1);
#ifdef HASH
                            //record_hash(new_frame->get_hash(), hitem(-(level + 1), pair, hashfALPHA)); //不换手, 依然是min层, 标记为hashfALPHA表示对于这个子节点来说其评价值至多为其评价值至多为pair.utility
                        }
#endif // HASH
                        delete new_frame->cur_board;
                        delete new_frame;
                    }

                    int child_utility = pair.utility;
                    if (new_pair.utility > child_utility)
                        new_pair = Pair({ steps_->at(i), child_utility });
                    if (flag)
                        if (child_utility <= a) { //alpha大于beta, 剪枝
                            delete steps_;
                            delete neighbors;
                            delete steps;
#ifdef HASH
                            //record_hash(frame->get_hash(), hitem(-level, new_pair, hashfEXACT));
#endif // HASH
                            return new_pair;
                        }

                    //#ifdef HASH
                    //                    if (new_pair.utility < b)
                    //                        hashf = hashfEXACT;
                    //#endif // HASH
                                        //子节点向上传递beta值(求min)
                    b = b < new_pair.utility ? b : new_pair.utility;
                }

                delete steps_;
                delete neighbors;
                delete steps;

#ifdef HASH
                //节点已经遍历完了, 那么对于这个节点记录到置换表里面的一定是准的
                record_hash(frame->get_hash(), hitem(-level, new_pair, hashfEXACT));
#endif // HASH
                return new_pair;
            }
        }
        else {
            //如果到达底层或者时间到了, 直接返回评估
            return Pair({ Step({-1, -1, -1}), evaluate(frame) });
        }
    }

    int get_safe_step_count(Board* board)
    {
        size_t key = board->get_bl_hash();
        auto it = _c_1.find(key);
        if (it != _c_1.end())
            return it->second;
        int ans = board->get_safe_step_count();
        _c_1.insert(std::make_pair(key, ans));
        return ans;
    }                                                         


    //得到剩余的安全边
    vector<Step> get_remain_safe_step(Board* board)
    {
        // 查缓存
        size_t key = board->get_line_hash();
        auto it = _c_2.find(key);
        if (it != _c_2.end())
            return it->second;

        vector<Step> ans; // 结果容器
        unordered_map<size_t, int> _cache; // 函数内缓存

        if (_c_2.size() >= 3000000) // 如果cache大小大于300w直接清除一次
        {
            unordered_map<size_t, vector<Step>>().swap(_c_2); // 清除
        }

        for (int i = 0; i < 5; i++)
            for (int j = 0; j < 5; j++)
                _cache.insert(std::make_pair(i * 10 + j, board->get_line_count(i, j)));

        //遍历格子
        for (int i = 0; i < 5; i++)
            for (int j = 0; j < 5; j++)
            {
                int count = _cache[i * 10 + j]; // 当前的格子有几条边被占领
                if (count == 0) // 当前格子是0分格子
                {
                    if (i - 1 >= 0 && _cache[(i - 1) * 10 + j] != 2) // 如果上边有格子并且上边格子不是二分格
                        ans.push_back({ 0, i - 1, j });
                    else if ( i - 1 < 0)
                        ans.push_back({ 0, i - 1, j });
                    if (j - 1 >= 0 && _cache[i * 10 + (j - 1)] != 2) // 如果左边有格子并且不是二分格
                        ans.push_back({ 1, j, i });
                    else if ( j - 1 < 0)
                        ans.push_back({ 1, j, i });
                    if (i + 1 <= 4 && _cache[(i + 1) * 10 + j] != 2) // 如果下边有格子并且不是二分格
                        ans.push_back({ 0, i, j });
                    else if (i + 1 > 4)
                        ans.push_back({ 0, i, j });
                    if (j + 1 <= 4 && _cache[i * 10 + (j + 1)] != 2) // 如果右边有格子, 并且右边格子不是二分格子
                        ans.push_back({ 1, j + 1, i });
                    else if (j + 1 > 4)// 如果右边没格子那一定是安全边
                        ans.push_back({ 1, j + 1, i });
                }
                if (count == 1) // 当前格子是一分格子
                {
                    if (board->line[0][i][j] == 0)
                    {
                        if (i - 1 >= 0 && _cache[(i - 1) * 10 + j] == 2)
                            ans.push_back({ 0, i - 1 , j });
                        else if (i - 1 < 0)
                            ans.push_back({ 0, i - 1 , j });
                    }   
                    if (board->line[0][i + 1][j] == 0)
                    {
                        if (i + 1 <= 4 && _cache[(i + 1) * 10 + j] == 2)
                            ans.push_back({ 0, i ,j });
                        else if (i + 1 > 4)
                            ans.push_back({ 0, i ,j });
                    }
                    if (board->line[1][j][i] == 0)
                    {
                        if (j - 1 >= 0 && _cache[i * 10 + (j - 1)] == 2)
                            ans.push_back({ 1, j, i });
                        else if ( j - 1 < 0)
                            ans.push_back({ 1, j, i });
                    }
                    if (board->line[1][j + 1][i] == 0)
                    {
                        if (j + 1 <= 4 && _cache[i * 10 + (j + 1)] == 2)
                            ans.push_back({ 1, j + 1, i });
                        else if (j + 1 > 4)
                            ans.push_back({ 1, j + 1, i });
                    }
                }

            }

        //去重
        std::set<Step> _s(ans.begin(), ans.end());
        vector<Step> _ans(_s.begin(), _s.end());
        

        _c_2.insert(std::make_pair(key, _ans)); // 缓存
        return _ans;
    }



    // 得到剩余安全步数的个数
    int get_remain_safe_count(Board* board)
    {
        // 查缓存
        size_t key = board->get_line_hash();
        auto it = _c_1.find(key);
        if (it != _c_1.end())   
            return it->second;

        int ans = 0;
        unordered_map<size_t, int> _cache; // 函数内缓存

        if (_c_1.size() >= 3000000) // 如果cache大小大于300w直接清除一次
        {
            unordered_map<size_t, int>().swap(_c_1); // 清除
        }

        for (int i = 0; i < 5; i++)
            for (int j = 0; j < 5; j++)
                _cache.insert(std::make_pair(i * 10 + j, board->get_line_count(i, j)));

        //遍历格子
        for (int i = 0; i < 5; i++)
            for (int j = 0; j < 5; j++)
            {
                int count = _cache[i * 10 + j]; // 当前的格子有几条边被占领
                if (count == 0) // 当前格子是0分格子
                {
                    int _neb_2_score_box_count = 0; // 临近二分格子数量
                    if (i - 1 >= 0)
                        if (_cache[(i - 1) * 10 + j] == 2)
                            _neb_2_score_box_count++;
                    if (j - 1 >= 0)
                        if (_cache[i * 10 + (j - 1)] == 2)
                            _neb_2_score_box_count++;
                    if (i + 1 <= 4)
                        if (_cache[(i + 1) * 10 + j] == 2)
                            _neb_2_score_box_count++;
                    if (j + 1 <= 4)
                         if (_cache[i * 10 + (j + 1)] == 2)
                            _neb_2_score_box_count++;

                    if (_neb_2_score_box_count == 3) // 如果临近二分格子数量是3则安全边数量是1
                    {
                        ans += 1;
                        continue;
                    }
                    else if (_neb_2_score_box_count == 4) // 如果临近二分格子数量是4则安全边数量是0
                    {
                        ans += 0;
                        continue;
                    }
                    ans += 2; // 其余情况安全边个数是2
                    continue;
                }

                if (count == 1) // 当前格子是一分格子
                {
                    int _neb_2_score_box_count = 0; // 临近二分格子数量
                    if (board->line[0][i][j] == 0)
                    {
                        if (i - 1 >= 0)
                            if (_cache[(i - 1) * 10 + j] == 2)
                            {
                                _neb_2_score_box_count++;
                            }
                    }
                    if (board->line[0][i + 1][j] == 0)
                    {
                        if (i + 1 <= 4)
                            if (_cache[(i + 1) * 10 + j] == 2)
                            {
                                _neb_2_score_box_count++;
                            }
                    }
                    if (board->line[1][j][i] == 0)
                    {
                        if (j - 1 >= 0)
                            if (_cache[i * 10 + (j - 1)] == 2)
                            {
                                _neb_2_score_box_count++;
                            }
                    }
                    if (board->line[1][j + 1][i] == 0)
                    {
                        if (j + 1 <= 4)
                            if (_cache[i * 10 + (j + 1)] == 2)
                            {
                                _neb_2_score_box_count++;
                            }
                    }

                    if (_neb_2_score_box_count >= 3) // 如果是一分格子并且相邻格子的二分格子数量大于等于3, 则没有安全边
                    {
                        ans += 0;
                        continue;
                    }
                    ans += 1; // 如果是一分格子并且相邻格子的二分格子数量小于3个, 则安全边数量是1
                    continue;
                }
        
            }
        _c_1.insert(std::make_pair(key, ans)); // 缓存
        return ans;
    }
    
    //评估
    int evaluate(Frame* frame)
    {
        int value = control_value(frame);
        return value;
    }

    int control_value(Frame* frame)
    {

        int control_value;//局面控制值
        int chains; //链数
        int long_chain = 0;  //长链数
        int loop;  //环数
        int double_;   //双交数
        ChainTable* temp = new ChainTable(frame->cur_board);
        chains = temp->chains.size();
        for (int i = 0; i < chains; i++)
        {
            if (temp->chains[i].available_steps.size() > 3)
            {
                long_chain++;
            }
        }
        loop = temp->loop.size()/4;
        double_ = temp->double_;
        chains -= loop;
        delete temp;
        int score = 0;

        //初始得分
        if (reference_player == RED)
        {
            score = 15 * frame->red_score - 15 * frame->blue_score;
        }
        else
        {
            score = 15 * frame->blue_score - 15 * frame->red_score;
        }
        //首先对于可吃分有一个评估
        if (reference_player == frame->turn)
        {
            score += 8 * frame->cur_board->get_box_count(3) - frame->cur_board->get_box_count(2);
            if (chains > 0 && (60 - frame->size) < 46)
            {
                //if ((60 - frame->size) < 46 && (60 - frame->size) > 5)
                //{
                //    //保持先手的先决条件//这里环测试不为长链，进行剔除了,即得分数总数为偶数，剩余步数为偶数的时候
                //    //1.链的条数为奇数,长链为偶数,短链为奇数
                //    if (chains % 2 == 1 && long_chain % 2 == 0 && (chains - long_chain) % 2 == 1 && (60 - frame->size + 1) % 2 == 0)
                //    {
                //        //一切在先决条件下进行下一步特殊判定
                //        score += 40;

                //    }
                //    else if (chains % 2 == 0 && long_chain % 2 == 1 && (chains - long_chain) % 2 == 0 && (60 - frame->size + 1) % 2 == 1)
                //    {
                //        score += 40;
                //    }
                //}
                //2.若当前还剩1个环，判定后面的2分格子大于8，即可进行让分,即构成2个双交
                if (loop == 1 && double_ == 2 && frame->cur_board->get_box_count(2) > 8)
                {
                    score += 600;
                }
                //3.若当前还剩0个环，判定后面的2分格子大于4，即可进行让分，即构成一个双交
                if (loop == 0 && double_ == 2 && frame->cur_board->get_box_count(2) > 4)
                {
                    score += 720;
                }
                //4.若当前还有2条短链，即到了1，3决杀步，这里会形成2个死格
                if (chains - long_chain == 2 && frame->cur_board->get_box_count(3) == 2 && frame->cur_board->get_box_count(2) > 4)
                {
                    score += 600;
                }
                //5.若当前没有短链了,即到了1决杀步,这里会形成2个死格
                if (chains - long_chain == 0 && frame->cur_board->get_box_count(3) == 2 && frame->cur_board->get_box_count(2) > 2)
                {
                    score += 730;
                }
                //6.若当前形成单一双交，并且没有短链的情况下，若后面2边大于2则进行让格,或者说还有一个环
                if (chains - long_chain == 0 && double_ == 1 && frame->cur_board->get_box_count(2) > 2 || loop == 1)
                {
                    score += 720;
                }
            }
        }
        else
        {
            score -= 8 * frame->cur_board->get_box_count(3) - frame->cur_board->get_box_count(2);
            if (chains > 0 && (60 - frame->size) < 46)
            {
                //if ((60 - frame->size) < 46 && (60 - frame->size) > 5)
                //{
                //    //保持先手的先决条件//这里环测试不为长链，进行剔除了,即得分数总数为偶数，剩余步数为偶数的时候
                //   //1.链的条数为奇数,长链为偶数,短链为奇数
                //    if (chains % 2 == 1 && long_chain % 2 == 0 && (chains - long_chain) % 2 == 1 && (60 - frame->size + 1) % 2 == 0)
                //    {
                //        //一切在先决条件下进行下一步特殊判定
                //        score -= 40;

                //    }
                //    else if (chains % 2 == 0 && long_chain % 2 == 1 && (chains - long_chain) % 2 == 0 && (60 - frame->size + 1) % 2 == 1)
                //    {
                //        score -= 40;
                //    }
                //}
                //2.若当前还剩1个环，判定后面的2分格子大于8，即可进行让分,即构成2个双交
                if (loop == 1 && double_ == 2 && frame->cur_board->get_box_count(2) > 8)
                {
                    score -= 600;
                }
                //3.若当前还剩0个环，判定后面的2分格子大于4，即可进行让分，即构成一个双交
                if (loop == 0 && double_ == 2 && frame->cur_board->get_box_count(2) > 4)
                {
                    score -= 720;
                }
                //4.若当前还有2条短链，即到了1，3决杀步，这里会形成2个死格
                if (chains - long_chain == 2 && frame->cur_board->get_box_count(3) == 2 && frame->cur_board->get_box_count(2) > 4)
                {
                    score -= 600;
                }
                //5.若当前没有短链了,即到了1决杀步,这里会形成2个死格
                if (chains - long_chain == 0 && frame->cur_board->get_box_count(3) == 2 && frame->cur_board->get_box_count(2) > 2)
                {
                    score -= 730;
                }
                //6.若当前形成单一双交，并且没有短链的情况下，若后面2边大于2则进行让格,或者说还有一个环
                if (chains - long_chain == 0 && double_ == 1 && frame->cur_board->get_box_count(2) > 2 || loop == 1)
                {
                    score -= 720;
                }
            }
        }
        return score;
    }


    void set_move_time(double time)
    {
        this->move_time = time;
    }

};



#endif // !ABSolver_CPP


